class Solution(object):
    '''
        以下是蛮力法，会超时！
    '''
    def minimumLevels_(self, possible):
        """
        :type possible: List[int]
        :rtype: int
        """
        for i in range(len(possible)-1):
            A_score = 0
            B_score = 0
            for j in range(i+1):
                if possible[j]:
                    A_score += 1
                else:
                    A_score -= 1
            for k in range(i+1, len(possible)):
                if possible[k]:
                    B_score += 1
                else:
                    B_score -= 1
            # print(A_score, B_score)
            if A_score > B_score:
                return i + 1
            else:
                if i == len(possible)-2:
                    return -1

    def judge(self, possible, mid):
        length = len(possible)
        Alength = mid+1
        Blength = length - Alength
        A_score = sum(possible[0:Alength]) - (Alength - sum(possible[0:Alength]))
        B_score = sum(possible[mid+1:length]) - (Blength - sum(possible[mid+1:length]))
        print("mid:%d;A:%d;B:%d" % (mid, A_score, B_score))
        if A_score > B_score:
            return True
        else:
            return False

    """
    * 企图用二分法来找到这个最小值，但是现实是其实这一道题并不满足二分查找的使用条件。
    * 虽然是按顺序来过关，序列是连续的，但是比如，第五关能满足，并不能说明第四关也就一定能满足。
    * 可以判断为，不满足单调的条件，所以不能用二分法。
    """
    def minimumLevels__(self, possible):
        """
        :type possible: List[int]
        :rtype: int
        """
        left = 0
        right = len(possible)-2

        while left < right:
            mid = (left + right) // 2
            if self.judge(possible, mid):
                right = mid
            else:
                left = mid + 1

        if self.judge(possible, left):
            print(left)
            return left+1
        else:
            return -1

    """
    学习陈剑的DP解法
    动态规划
    """
    def minimumLevels(self, possible):
        length = len(possible)
        # 构建动态规划的表，用来计算出选手分别完成从[0,n]关的最终得分
        dp = [0] * (length + 1)
        for i in range(length):
            if possible[i] == 0:
                dp[i+1] = dp[i] - 1
            else:
                dp[i+1] = dp[i] + 1
        # 由于得分具有可以累加的特性，所以对于另一位选手的得分的计算，我们只需要通过全通关的得分减去第一位选手的得分即可
        res = -1
        # 从少到多(最多只允许到倒数第二位，因为每个人至少要过1关)遍历得到两位选手的最终得分，并比较
        for i in range(1, length):
            score_A = dp[i]
            score_B = dp[length] - score_A
            if score_A > score_B:
                res = i
                break
        return res